﻿using System;

namespace 排序算法
{
    class Program
    {
        static void Main(string[] args)
        {
            var arr = new int[10];
            //生成10个10-100的随机数
            for (int i = 0; i < 10; i++)
            {
                arr[i] = new Random().Next(10, 100);
            }
            Console.WriteLine("原始数组");
            foreach (var item in arr)
            {
                Console.Write(item+",");
            }
            var newArr = ShellSort(arr);
            Console.WriteLine("\n");
            Console.WriteLine("排序后数组");
            foreach (var item in newArr)
            {
                Console.Write(item+",");
            }
            Console.ReadKey();
        }
        //冒泡排序(左到右)
        public static int[] BubbleSort(int[] arr)
        {
            int temp;
            for (int i = 0; i < arr.Length-1; i++)
            {
                for (int j = 1; j < arr.Length-i-1; j++)
                {
                    if (arr[j - 1] > arr[j])
                    {
                        temp = arr[j - 1];
                        arr[j - 1] = arr[i];
                        arr[i] = temp;
                    }
                }
            }
            return arr;
        }
        //插入排序
        public static int[] InsertSort(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                int t = arr[i];
                int j = i;
                while ((j > 0) && (arr[j - 1] > t))
                {
                    arr[j] = arr[j - 1];
                    --j;
                }
                arr[j] = t;
            }
            return arr;
        }
        //选择排序
        public static int[] SelectSort(int[] arr)
        {
            int min;
            for (int i = 0; i < arr.Length - 1; i++)
            {
                min = i;
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[min])
                        min = j;
                }
                int t = arr[min];
                arr[min] = arr[i];
                arr[i] = t;
            }
            return arr;
        }
        //快速排序
        #region
        public static int[] QuickSort(int[] arr)
        {
            return QuickSortStrict(arr, 0, arr.Length - 1);
        }
        public static int[] QuickSortStrict(int[] data, int low, int high)
        {
            if (low >= high) return data;
            int temp = data[low];
            int i = low + 1, j = high;
            while (true)
            {
                while (data[j] > temp) j--;
                while (data[i] < temp && i < j) i++;
                if (i >= j) break;
                Swap(data, i, j);
                i++; j--;
            }
            if (j != low)
                Swap(data, low, j);
            QuickSortStrict(data, j + 1, high);
            QuickSortStrict(data, low, j - 1);
            return data;
        }

        //交换
        public static void Swap(int[] data,int a, int b)
        {
            int temp = data[a];
            data[a] = data[b];
            data[b] = temp;
        }
        #endregion

        //希尔排序
        public static int[] ShellSort(int[] arr)
        {
            int inc;
            for (inc = 1; inc <= arr.Length / 9; inc = 3 * inc + 1) ;
            for (; inc > 0; inc /= 3)
            {
                for (int i = inc + 1; i <= arr.Length; i += inc)
                {
                    int t = arr[i - 1];
                    int j = i;
                    while ((j > inc) && (arr[j - inc - 1] > t))
                    {
                        arr[j - 1] = arr[j - inc - 1];
                        j -= inc;
                    }
                    arr[j - 1] = t;
                }
            }
            return arr;
        }
    }
}
